/*
 * Basado en el libro de Duane A. Bailey, "Java Structures", pág. 321-326
 */
package Hoja6;

import java.util.Vector;

/**
 *
 * @param <E> 
 * @author María Fernanda Martínez
 */
public class VectorHeap <E extends Comparable> {
    /**
     * Los datos, guardados en orden
     */
    protected Vector<E> data; 
    
    /**
     * Nombre: VectorHeap
     * Descripción: constructor de la clase
     * Pre: no hay
     * Post: construye una nueva cola con prioridad
     * No hay parámetros ni valor de retorno
     */
    public VectorHeap()
    {
        data = new Vector<E>();
    }
    
    /**
     * Nombre: VectorHeap
     * Descripción: constructor de la clase con valor inicial
     * Pre: v no es null
     * Post: construye una nueva cola con prioridad de un vector desordenado
     * No hay valor de retorno
     * @param v
     */
    public VectorHeap(Vector<E> v)
    {
        int i;
        data = new Vector<E>(v.size()); // se conoce el tamaño
        for (i = 0; i < v.size(); i++)
        { // agregar elementos al heap
            add(v.get(i));
        }
    }
    
    /**
     * Nombre: parent
     * Descripción: obtener el valor de parent
     * Pre: 0 <= i < size
     * Post: regresa padre del nodo en la posición i
     * @param i
     * @return
     */
    protected static int parent(int i)
    {
        return (i-1)/2;
    }
    
    /**
     * Nombre: left
     * Descripción: obtener el valor de left
     * Pre: 0 <= i < size
     * Post: regresa índice del subárbol izquierdo en la locación i
     * @param i
     * @return
     */
    protected static int left(int i)
    {
        return 2*i+1;
    }
    
    /**
     * Nombre: right
     * Descripción: obtener el valor de right
     * Pre: 0 <= i < size
     * Post: regresa índice de subárbol derecho del nodo en la locación i
     * @param i
     * @return
     */
    protected static int right(int i)
    {
        return 2*(i+1);
    }
    
    /**
     * Nombre: percolateUp
     * Descripción: subir un subárbol un nivel, es decir, volver padre a un hijo
     * Pre: 0 <= leaf < size
     * Post: mueve nodo en posición leaf hacia arriba a una posición adecuada
     * @param leaf
     */
    protected void percolateUp(int leaf)
    {
        int parent = parent(leaf);
        E value = data.get(leaf);
        while (leaf > 0 && (value.compareTo(data.get(parent)) < 0))
        {
            data.set(leaf,data.get(parent));
            leaf = parent;
            parent = parent(leaf);
        }
        data.set(leaf,value);
    }
    
    /**
     * Nombre: add
     * Descripción: agregar un valor al heap
     * Pre: value no es null e implementa comparable
     * Post: valor agregado al heap
     * No hay valor de retorno
     * @param value
     */
    public void add(E value)
    {
        data.add(value);
        percolateUp(data.size()-1);
    }
    
    /**
     * Nombre: pushDownRoot
     * Descripción: bajar un padre a la categoría de hijo
     * Pre: 0 <= root < size
     * Post: mueve nodo en la posición root a su posición adecuada como subárbol
     * No hay valor de retorno
     * @param root
     */
    protected void pushDownRoot(int root)
    {
        int heapSize = data.size();
        E value = data.get(root);
        while (root < heapSize) {
            int childpos = left(root);
            if (childpos < heapSize)
            {
                if ((right(root) < heapSize) && ((data.get(childpos+1)).compareTo(data.get(childpos)) < 0))
                {
                    childpos++;
                }
                
                if ((data.get(childpos)).compareTo(value) < 0)
                {
                    data.set(root,data.get(childpos));
                    root = childpos; // Seguir bajando
                } else { // Encontrar posición correcta
                    data.set(root,value);
                    return;
                }
            } else { // En un extremo, insertar y salir
                data.set(root,value);
                return;
            }
        }
    }
    
    /**
     * Nombre: remove
     * Descripción: remover un valor del heap
     * Pre: no está vacío
     * Post: regresa y remueve el mínimo valor de la cola
     * @return
     */
    public E remove()
    {
        E minVal = getFirst();
        data.set(0,data.get(data.size()-1));
        data.setSize(data.size()-1);
        if (data.size() > 1) pushDownRoot(0);
        return minVal;
    }
    
    /**
     * Nombre: getFirst
     * Descripción: obtiene el primer elemento de la cola
     * Pre: la cola no está vacía
     * Post: regresa valor más pequeño en la cola
     * @return
     */
    public E getFirst()
    {
        return data.get(0);
    }
    
    /**
     * Nombre: size
     * Descripción: obtener el tamaño de la cola
     * Pre: no hay
     * Post: regresa el tamaño de la cola
     * No hay parámetro
     * @return
     */
    public int size(){
        return data.size();
    }
}